import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/28 19:20
 */
public class 字符串 {
    /*
     * #problem 709 转换为小写字母
     * */
    public String toLowerCase(String s) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (c >= 'A' && c <= 'Z') {
                arr[i] = (char) (c + 32);
            }
        }
        return String.valueOf(arr);
    }

    /*
     * #problem 58 最后一个单词的长度
     * */
    // 1. 从后往前遍历
    public int lengthOfLastWord(String s) {
        int len = 0;
        int i = s.length() - 1;
        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }
        while (i >= 0 && s.charAt(i) != ' ') {
            len++;
            i--;
        }
        return len;
    }

    /*
     * #problem 771 宝石与石头
     * */
    public int numJewelsInStones(String jewels, String stones) {
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for (char s : jewels.toCharArray()) {
            if (s >= 'A' && s <= 'Z') {
                count1[s - 'A']++;
            } else {
                count2[s - 'a']++;
            }
        }
        int res = 0;
        for (char s : stones.toCharArray()) {
            if (s >= 'A' && s <= 'Z') {
                res += count1[s - 'A'] > 0 ? 1 : 0;
            } else {
                res += count2[s - 'a'] > 0 ? 1 : 0;
            }
        }
        return res;
    }

    /*
     * #problem 387 字符串中的第一个唯一字符
     * */
    public int firstUniqChar(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (count[c - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }

    /*
     * #problem 8 字符串转换正数(atoi)
     * */
    public int myAtoi(String s) {
        // 处理前导空格
        int i = 0, len = s.length();
        while (i < len && s.charAt(i) == ' ') {
            i++;
        }
        int flag = 1;
        int res = 0;
        int start = i;
        while (i < len && s.charAt(i) != ' ') {
            if (s.charAt(i) == '-' && start == i) {
                flag = -1;
            } else if (s.charAt(i) == '+' && start == i) {
                flag = 1;
            } else if (Character.isDigit(s.charAt(i))) {
                int num = s.charAt(i) - '0';
                if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && num > Integer.MAX_VALUE % 10)) {
                    return Integer.MAX_VALUE;
                } else if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && -num < Integer.MIN_VALUE % 10)) {
                    return Integer.MIN_VALUE;
                }
                res = res * 10 + flag * num;
            } else {
                break;
            }
            i++;
        }
        return res;
    }


    /*
     * #problem 14 最长公共前缀
     * */
    // 1. 竖着看
    public String longestCommonPrefix(String[] strs) {
        StringBuilder res = new StringBuilder();
        int i = 0;
        while (i < strs[0].length()) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return res.toString();
                }
            }
            res.append(c);
            i++;
        }
        return res.toString();
    }


    /*
     * #problem 344 反转字符串
     * */
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char t = s[left];
            s[left] = s[right];
            s[right] = t;
            left++;
            right--;
        }
    }

    /*
     * #problem 541 反转字符串II
     * */
    // 1. 反转2k个字符的前k个字符
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        if (s.length() <= k) {
            reverse(arr, 0, s.length() - 1);
            return String.valueOf(arr);
        }
        int right = 2 * k - 1;
        int left = 0;
        for (; right < s.length(); right += 2 * k) {
            reverse(arr, left, right - k);
            left = right + 1;
        }
        if (s.length() - left >= k) {
            reverse(arr, left, left + k - 1);
        } else {
            reverse(arr, left, s.length() - 1);
        }
        return String.valueOf(arr);
    }

    // 2. 第二种写法
    public String reverseStr2(String s, int k) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < s.length(); i += (2 * k)) {
            if (i + k > s.length()) {
                reverse(arr, i, s.length() - 1);
            } else {
                reverse(arr, i, i + k - 1);
            }
        }
        return String.valueOf(arr);
    }

    private void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char t = arr[left];
            arr[left] = arr[right];
            arr[right] = t;
            left++;
            right--;
        }
    }

    /*
     * #problem 151 反转字符串中的单词
     * */
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        // 反转整体
        reverse(arr, 0, arr.length - 1);
        // 反转每个单词
        StringBuilder res = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            // 处理空格
            while (i < s.length() && arr[i] == ' ') {
                i++;
            }
            int j = i;
            while (j < s.length() && arr[j] != ' ') {
                j++;
            }
            reverse(arr, i, j - 1);
            if (res.length() != 0 && i != j) {
                res.append(" ");
            }
            res.append(String.valueOf(arr, i, j - i));
            i = j;
        }
        return res.toString();
    }

    // 2. 写法2
    public String reverseWords2(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }

    /*
     * #problem 557 反转字符串中的单词II
     * 比起上一题，该题的测试数据的边界条件比较少
     * 没有前后置空格，每个单词之间只隔一个空格
     * */
    public String reverseWordsII(String s) {
        char[] arr = s.toCharArray();
        int i = 0;
        while (i < s.length()) {
            while (i < s.length() && arr[i] == ' ') {
                i++;
            }
            int j = i;
            while (j < s.length() && arr[j] != ' ') {
                j++;
            }
            reverse(arr, i, j - 1);
            i = j + 1;
        }
        return String.valueOf(arr);
    }

    /*
     * #problem 917 仅仅反转字母
     * */
    public String reverseOnlyLetters(String s) {
        char[] arr = s.toCharArray();
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetter(arr[left])) {
                left++;
            }
            while (left < right && !Character.isLetter(arr[right])) {
                right--;
            }
            if (left < right) {
                char t = arr[left];
                arr[left++] = arr[right];
                arr[right--] = t;

            }
        }
        return String.valueOf(arr);
    }

    /*
     * #problem 242 有效的字母异位词
     * */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int i : count) {
            if (i != 0) {
                return false;
            }
        }

        return true;
    }

    /*
     * #problem 49 字母异位词分组
     * */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> memo = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < count.length; i++) {
                if (count[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(count[i]);
                }
            }
            String key = sb.toString();
            memo.putIfAbsent(key, new ArrayList<>());
            memo.get(key).add(s);
        }
        return new ArrayList<>(memo.values());
    }

    /*
     * #problem 438 找到字符串中所有字母异位词
     * */
    // 1. 找到s中所有p的异位词的子串 ==> 子串：滑动窗口
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int len = p.length();
        int[] count = new int[26];
        for (char c : p.toCharArray()) {
            count[c - 'a']++;
        }
        int left = 0, right = 0;
        int[] count2 = new int[26];
        for (; right < s.length(); right++) {
            char c = s.charAt(right);
            // 入队
            count2[c - 'a']++;
            if (right - left + 1 == len) {
                // 判断，且进行出队操作
                int i = 0;
                while (i < count2.length) {
                    if (count[i] != count2[i]) {
                        break;
                    }
                    i++;
                }
                if (i >= count2.length) {
                    res.add(left);
                }
                // 出队操作
                char c1 = s.charAt(left);
                count2[c1 - 'a']--;
                left++;
            }

        }

        return res;
    }

    /*
     * #problem 125 验证回文串
     * */
    // 1. 从中间向两边扩散
    public boolean isPalindrome(String s) {
        // 处理非字母字符
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetter(c)) {
                sb.append(Character.toLowerCase(c));
            } else if (Character.isDigit(c)) {
                sb.append(c);
            }
        }
        int len = sb.length();
        int left = 0, right = 0;
        if ((len & 1) != 0) {
            // 奇数
            left = right = len / 2;
        } else {
            // 偶数
            left = len / 2 - 1;
            right = len / 2;
        }
        while (left >= 0 && right < sb.length()) {
            if (sb.charAt(left) != sb.charAt(right)) {
                return false;
            }
            left--;
            right++;
        }
        return true;
    }

    // 2. 在原字符上进行判断
    public boolean isPalindrome2(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (left < right) {
                if (Character.toUpperCase(s.charAt(left)) != Character.toUpperCase(s.charAt(right))) {
                    return false;
                }
            }
            left++;
            right--;
        }
        return true;
    }

    /*
     * #problem 680 验证字符串II
     * 最多可以删除一个字符
     * */
    // 1. 删除left 和 删除right这两种情况都要考虑
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // 删除 left 或者 删除 Right
                return validPalindrome(s, left + 1, right) || validPalindrome(s, left, right - 1);
            } else {
                left++;
                right--;
            }
        }
        return true;
    }

    private boolean validPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /*
     * #problem 5 最长回文子串
     * */
    // 1. 枚举中心点，向外扩展
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = customValidPalindrome(s, i, i);
            int len2 = customValidPalindrome(s, i, i + 1);
            int len = Math.max(len2, len1);
            if (len >= end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int customValidPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && (s.charAt(left) == s.charAt(right))) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    /*
     * #problem 1143 最长公共子序列
     * */
    // 1. 使用动态规划 ==> dp[i][j] : s[i..j]的最长公共子序列长度
    // s[i] == s[j] ==> dp[i][j] = dp[i-1][j-1] +1
    // s[i] != s[j] ==> max(dp[i-1][j],dp[i][j-1])
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(), len2 = text2.length();
        int[][] dp = new int[len1][len2];
        int fill = 0;
        for (int i = 0; i < len2; i++) {
            if (text1.charAt(0) == text2.charAt(i)) {
                fill = 1;
            }
            dp[0][i] = fill;
        }
        fill = 0;
        for (int i = 0; i < len1; i++) {
            if (text1.charAt(i) == text2.charAt(0)) {
                fill = 1;
            }
            dp[i][0] = fill;
        }
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1 - 1][len2 - 1];
    }


    /*
     * #problem 72 编辑距离
     * */
    // 1. 动态规划
    /*
     * dp[i][j] ==> word1[0..i] ==> 转换为 word2[0...j] 需要的最少操作
     * word1[i] == word2[j] ==> dp[i][j] = dp[i-1][j-1]
     * word1[i] != word2[j] ==> dp[i-1][j] + word2添加i || dp[i][j-1] + word1 添加j
     * */
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= len2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                int replace = dp[i - 1][j - 1];
                int a_insert = dp[i][j - 1] + 1;
                int b_insert = dp[i - 1][j] + 1;
                if (word2.charAt(j - 1) != word1.charAt(i - 1)) {
                    replace += 1;
                }
                dp[i][j] = Math.min(replace, Math.min(a_insert, b_insert));
            }
        }
        return dp[len1][len2];
    }

    /*
     * #problem 10 正则表达式匹配
     * */
    // 1. 正则表达式
    /*
     *  dp[i][j] ==> s[0..i] 是否与 p[0..j]匹配
     * dp[i][j] ==>
     * 1. p[j]为字符 ==> dp[i][j] = dp[i-1][j-1] & s[i] == p[j]
     * 2. p[j]为'*' ==> s[i] 需要与 p[j-1]进行匹配，可以是0次，也可以是n次 ==> dp[i][j] = dp[i][j-2] (匹配0次）
     * 如果是n次 ==> n次其实可以归纳为一次 ==> 如果当前匹配成功，则将s末尾匹配成功的那个字符移除，然后再进行匹配，也就是 dp[i][j] = dp[i-1][j]
     * 3. p[j]为'.' ==> 匹配
     * 边界条件 ： dp[0][0] = true,空字符匹配肯定成功
     * */
    public boolean isMatch(String s, String p) {
        int len1 = s.length(), len2 = p.length();
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        // s为空串，只有当p也为空串的情况下才匹配，或者#*#*..这种情况也是匹配的，但测试例子应该不会有这个
        dp[0][0] = true;
        for (int i = 0; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (p.charAt(j - 1) == '*') {
                    // 匹配0次
                    dp[i][j] = dp[i][j - 2];
                    if (i != 0 && match(s, i - 1, p, j - 2)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    if (i != 0) {
                        dp[i][j] = dp[i - 1][j - 1] && match(s, i - 1, p, j - 1);
                    }
                }
            }
        }
        return dp[len1][len2];
    }

    // 2. 动态规划 --写法2
    public boolean isMatch2(String s, String p) {
        int len1 = s.length(), len2 = p.length();
        boolean[][] f = new boolean[len1 + 1][len2 + 1];
        f[0][0] = true;
        // 处理 dp[0][j]的问题
        // 只有出现 x*d*f* 的情况，才会匹配空串
        for (int j = 2; j <= len2; j++) {
            if (p.charAt(j) == '*') {
                f[0][j] = f[0][j - 2];
            }
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (p.charAt(j - 1) == '*') {
                    // 匹配0次
                    f[i][j] = f[i][j - 2];
                    // 判断s是否与p[j-1]个字符匹配
                    if (match(s, i - 1, p, j - 2)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    f[i][j] = f[i - 1][j - 1] && match(s, i - 1, p, j - 1);
                }
            }
        }

        return f[len1][len2];
    }

    private boolean match(String s, int index1, String p, int index2) {

        if (p.charAt(index2) == '.') {
            return true;
        }
        return s.charAt(index1) == p.charAt(index2);
    }

    /*
     * #problem 44 通配符匹配
     * */
    // 1. 动态规划 ==> 注意与上面题目的区分 （*的作用）这里*可以匹配任意字符串，不需要看前置字符
    /*
     * 所以当 p[j]为*时，有两种情况 ：  1. *匹配一个空的字符串 ==> dp[i][j] = dp[i][j-1]
     * 2.  * 匹配N次 ==> dp[i-1][j] (每匹配一次，其实就是将s的末尾字符剪掉一个，然后再和p进行比较）
     * */
    public boolean isMatchII(String s, String p) {
        int len1 = s.length(), len2 = p.length();
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        for (int i = 1; i <= len2; i++) {
            if (p.charAt(i - 1) == '*') {
                // 0次匹配
                dp[0][i] = dp[0][i - 1];
            }
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && match2(s, i - 1, p, j - 1);
                }
            }
        }
        return dp[len1][len2];
    }

    private boolean match2(String s, int s1, String p, int p1) {
        if (p.charAt(p1) == '?') {
            return true;
        }
        return s.charAt(s1) == p.charAt(p1);
    }


    /*
     * #problem 115 不同的子序列
     * 在s子序列中t出现的个数
     * */
    // 1. 动态规划 dp[i][j] ==> s[..i]的子序列 中出现多少个 t[..j]
    /*
     * dp[i][j]的取值情况分为两种情况：
     * 1. s[i] == t[j] ==> 这时我们可以选择将 s[i] 加入到匹配中，也就是说，s[i]作为子序列的一部分,这种情况下，子序列会出现多少个t[..j] ==> dp[i-1][j-1]
     * s[i]不加入到匹配中，也就是说不选择s[i]，子序列中没有s[i]，那么此时s[..i]的子序列会出现多少个t[..j] ==> dp[i-1][j]
     * 2. s[i] != t[j] ==> dp[i-1][j];
     * */
    public int numDistinct(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // 需要选择 s[i] 是否与 s[j]进行匹配
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len1][len2];
    }


    /*
     * #problem 205 同构字符串
     * s 可以通过某种映射关系 映射到t
     * s有几个不同字符 --> t也要有几个不同字符
     * s 每个字符出现的个数 与 t中字符出现的次数 (不行，不能改变字符的顺序)
     * 记录映射就可以了
     * */
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        Map<Character,Character> mapper = new HashMap<>();
        int[] visited = new int[128];
        // 记录映射 和 已经被映射的字符
        for(int i =0;i<s.length();i++) {
            char s1 = s.charAt(i);
            char t1 = t.charAt(i);
            if(!mapper.containsKey(s1) ) {
                if(visited[t1] == 0) {
                    mapper.put(s1,t1);
                    visited[t1] ++;
                } else {
                    return false;
                }
            } else if(mapper.get(s1) != t1) {
                return false;
            }
        }
        return true;
    }

    public boolean isIsomorphic2(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        int[] s2t = new int[128];
        int[] visited = new int[128];
        for(int i =0;i<s.length();i++) {
            char s1 = s.charAt(i);
            char t1 = t.charAt(i);
            if(s2t[s1] == 0) {
                if(visited[t1] != 0) {
                    return false;
                } else {
                    s2t[s1] = t1;
                    visited[t1] = 1;
                }
            } else if(s2t[s1] != (int)t1){
                return false;
            }
        }
        return true;
    }


    /*
    * #problem 32 最长有效括号
    * dp[i] ==> 以i结尾的 最长括号子串长度
    * */
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int max = 0;
        for(int i =1;i<s.length();i++) {
            char c = s.charAt(i);
            if(c == '(') {
                dp[i] = 0;
            } else {
                if(s.charAt(i-1) == '(') {
                    dp[i] = i-2>=0? dp[i-2] + 2 : 2;
                } else {
                    int k = i-1-dp[i-1];
                    if(k>=0 && s.charAt(k) == '(') {
                        dp[i] = (k-1) >=0 ? dp[i-1] + dp[k-1] + 2 : dp[i-1] + 2;
                    }
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }

}
